package search.backtracking;

import java.util.Arrays;

/**
 * @Classname : UniquePaths
 * @Description : 62. 不同路径
 * https://leetcode.cn/problems/unique-paths/
 * @Author : chentianyu
 * @Date 2023/3/19 00:01
 */


public class UniquePaths {
    private int count;
    boolean[][] visited;
    int[][] memory;

    public int uniquePaths(int m, int n) {
        count = 0;
        visited = new boolean[m][n];
        memory = new int[m][n];
        for (int i = 0; i < m; i++) Arrays.fill(memory[i], -1);

        backTracking(m, n, 0, 0);
        return count;
    }

    private int backTracking(int m, int n, int x, int y) {
        // 出界或已遍历情况
        if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) return 0;
        // 到达目标网格情况
        if (x == m - 1 && y == n - 1) {
            count++;
            return 1;
        }
        // 使用记忆结果
        if (memory[x][y] != -1) {
            count += memory[x][y];
            return memory[x][y];
        }

        visited[x][y] = true;
        memory[x][y] = 0;
        memory[x][y] += backTracking(m, n, x + 1, y);  // 下
        memory[x][y] += backTracking(m, n, x, y + 1);  // 右
        visited[x][y] = false;
        return memory[x][y];
    }
}
